/**
 * Copyright 2013 The FROG Brigade
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package net.frogbrigade.bufonidae.util.sort;

/**
 * Tony Hoareが考案したQuicksortアルゴリズムを利用するソートです。
 * <p>
 * このアルゴリズムでは、平均計算量はO(n log
 * n)で、最大計算量はO(n2)となります。又、指定するComparableインターフェースの実装によりますが、安定ソートではありません。
 * 
 * @author nobuyuki sekimori
 * @since 1.0.0
 * @version 1.0.0
 */
public class QuickSort
{
    /**
     * オブジェクトを生成します。
     */
    private QuickSort()
    {
    }

    /**
     * 指定したオブジェクト配列を昇順にソートします。
     * <p>
     * 指定する配列の要素はComparableインターフェースを実装している必要があります。
     * 
     * @param arr
     *            ソートするオブジェクト配列です。
     */
    public static <E extends Comparable<? super E>> void sort(E[] arr)
    {
        QuickSort.sort(arr, 0, arr.length - 1);
    }

    /**
     * 指定したオブジェクト配列の指定した範囲を昇順にソートします。
     * <p>
     * ソートの範囲は、オブジェクト配列の先頭の要素のインデックスを含み、末尾の要素のインデックスを含みません。
     * 指定する配列の要素はComparableインターフェースを実装している必要があります。
     * 
     * @param arr
     *            ソートするオブジェクト配列です。
     * @param minIndex
     *            ソートする先頭の要素のインデックスです。
     * @param maxIndex
     *            ソートする末尾の要素のインデックスです。
     */
    public static <E extends Comparable<? super E>> void sort(E[] arr, int minIndex, int maxIndex)
    {
        if (minIndex < maxIndex)
        {
            int midIndex = minIndex + (maxIndex - minIndex) / 2;
            int partition = QuickSort.computePartition(arr, minIndex, midIndex, maxIndex);

            QuickSort.sort(arr, minIndex, partition - 1);
            QuickSort.sort(arr, partition + 1, maxIndex);
        }
    }

    /**
     * 指定したオブジェクト配列をソートするためにパーティションを算出して返します。
     * 
     * @param arr
     *            パーティションを算出するオブジェクト配列です。
     * @param minIndex
     *            パーティションを算出する先頭の要素のインデックスです。
     * @param midIndex
     *            パーティションを算出する中央の要素のインデックスです。
     * @param maxIndex
     *            パーティションを算出する末尾の要素のインデックスです。
     * @return 算出したパーティションです。
     */
    private static <E extends Comparable<? super E>> int computePartition(E[] arr, int minIndex, int midIndex, int maxIndex)
    {
        E pivot = arr[midIndex];
        QuickSort.swapElement(arr, midIndex, maxIndex);

        int partition = minIndex;

        for (int i = minIndex; i < maxIndex; i++)
        {
            if (arr[i].compareTo(pivot) <= 0)
            {
                QuickSort.swapElement(arr, i, partition);
                partition++;
            }
        }

        QuickSort.swapElement(arr, partition, maxIndex);

        return partition;
    }

    /**
     * 指定したオブジェクト配列の要素同士をスワップします。
     * 
     * @param arr
     *            要素をスワップするオブジェクト配列です。
     * @param elmIndex1
     *            スワップする1番目の要素のインデックスです。
     * @param elmIndex2
     *            スワップする2番目の要素のインデックスです。
     */
    private static <E extends Comparable<? super E>> void swapElement(E[] arr, int elmIndex1, int elmIndex2)
    {
        E tmp = arr[elmIndex1];
        arr[elmIndex1] = arr[elmIndex2];
        arr[elmIndex2] = tmp;
    }
}